package class21;

/**
 * @author YZY
 * @since 2022/8/22 14:28
 * <a href="https://leetcode.cn/problems/coin-change-2/">518. 零钱兑换 II</a>
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的方法数
 * 例如：arr = {1,2}，aim = 4
 * 方法如下：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 */
public class Code03_CoinsWayNoLimit {

    /**
     * 暴力尝试 - 从左往右尝试模型
     */
    public static int change1(int amount, int[] coins) {
        return process1(coins, 0, amount);
    }

    private static int process1(int[] coins, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int count = 0; count * coins[index] <= rest; ++count) {
            ways += process1(coins, index + 1, rest - (count * coins[index]));
        }
        return ways;
    }

    /**
     * 记忆化搜索
     */
    public static int change2(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        return process2(coins, 0, amount, dp);
    }

    private static int process2(int[] coins, int index, int rest, int[][] dp) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        if (dp[index][rest] != 0) {
            return dp[index][rest];
        }
        int ways = 0;
        for (int count = 0; count * coins[index] <= rest; ++count) {
            ways += process2(coins, index + 1, rest - (count * coins[index]), dp);
        }
        return dp[index][rest] = ways;
    }

    /**
     * 动态规划
     */
    public static int change3(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; --index) {
            for (int rest = 0; rest <= amount; ++rest) {
                int ways = 0;
                for (int count = 0; count * coins[index] <= rest; ++count) {
                    ways += dp[index + 1][rest - (count * coins[index])];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][amount];
    }

    /**
     * 动态规划 - 状态压缩
     */
    public static int change4(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; --index) {
            for (int rest = 0; rest <= amount; ++rest) {
                // 状态压缩，只依赖于左边和下边，左边是左下的前缀和
                dp[index][rest] = dp[index + 1][rest];
                dp[index][rest] += rest >= coins[index] ? dp[index][rest - coins[index]] : 0;
            }
        }
        return dp[0][amount];
    }

    // 为了测试
    public static int[] randomArray(int maxLen, int maxValue) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        boolean[] has = new boolean[maxValue + 1];
        for (int i = 0; i < N; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue) + 1;
            } while (has[arr[i]]);
            has[arr[i]] = true;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 为了测试
    public static void main(String[] args) {
        int maxLen = 10;
        int maxValue = 30;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = change1(aim, arr);
            int ans2 = change4(aim, arr);
            int ans3 = change3(aim, arr);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println(ans3);
                break;
            }
        }
        System.out.println("测试结束");
    }

}
